﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BinaryTreeCode
{
    class DepthOfTree
    {

        //================================力扣104 二叉树的最大深度
        //给定一个二叉树，找出其最大深度
        //最大深度为根节点到最远叶子节点的最长路径上的节点数
        //叶子节点是指没有子节点的节点
        public int MaxDepth(TreeNode root)
        {
            //层序遍历
            Queue<TreeNode> que = new Queue<TreeNode>();
            if (root != null)
                que.Enqueue(root);

            int depth = 0;

            while (que.Count > 0)
            {
                depth++;
                int size = que.Count;

                for (int i = 0; i < size; i++)
                {
                    TreeNode node = que.Dequeue();

                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                }

            }
            return depth;
        }
        //递归法
        //前序递归求的是深度，后序求的是高度，跟根节点的高度就是二叉树的最大深度
        public int MaxDepth_2(TreeNode root)
        {//后序递归
            return Getdepth(root);
        }
        int Getdepth(TreeNode node)
        {
            if (node == null)
                return 0;
            int leftdepth = Getdepth(node.left);//左
            int rightdepth = Getdepth(node.right);//右
            int depth = 1 + Math.Max(leftdepth, rightdepth);//中，加1是因为算上当前中间节点
            return depth;
        }
        //前序递归
        public int MaxDepth_3(TreeNode root)
        {
            result = 0;
            if (root == null)
                return result;
            Getdepth(root, 1);
            return result;
        }
        private int result;
        void Getdepth(TreeNode node,int depth)
        {
            result = Math.Max(result, depth);//中

            if (node.left == null && node.right == null)
                return;

            if(node.left != null)
            {//左
                depth++;//深度+1
                Getdepth(node.left, depth);//
                depth--;//回溯，深度-1
            }

            if(node.right != null)
            {//右
                depth++;
                Getdepth(node.right, depth);
                depth--;
            }
        }

        //==================================力扣559 N叉树的最大深度
        //给定一个N叉树，找到其最大深度
        public int MaxDepth_4(TreeNodeN root)
        {

            return GetDpeth_2(root);
        }
        int GetDpeth_2(TreeNodeN root)
        {//前序递归
            if (root == null)
                return 0;

            int depth = 0;
            for(int i = 0;i<root.children.Count;i++)
            {
                depth = Math.Max(depth, GetDpeth_2(root.children[i]));//子节点
            }
            depth++;//中
            return depth;
        }

        //层序遍历
        public int MaxDepth_5(TreeNodeN root)
        {
            Queue<TreeNodeN> que = new Queue<TreeNodeN>();
            if (root != null)
                que.Enqueue(root);
            int depth = 0;
            while(que.Count > 0)
            {
                int size = que.Count;
                depth++;
                for(int i = 0;i<size;i++)
                {
                    TreeNodeN node = que.Dequeue();
                    for(int j = 0;j<node.children.Count;j++)
                    {
                        que.Enqueue(node.children[j]);
                    }
                }
            }
            return depth;
        }

        //==================================力扣111 二叉树的最小深度
        //给定一个二叉树，找出其最小深度。
        //最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
        //说明：叶子节点是指没有子节点的节点。
        public int MinDepth(TreeNode root)
        {
            //层序遍历
            //只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点
            Queue<TreeNode> que = new Queue<TreeNode>();
            if (root != null)
                que.Enqueue(root);

            int depth = 0;

            while (que.Count > 0)
            {
                depth++;
                int size = que.Count;

                for (int i = 0; i < size; i++)
                {
                    TreeNode node = que.Dequeue();

                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                    if (node.right == null && node.left == null)
                        return depth;
                }
            }
            return depth;
        }

        //递归
        int GetMinDep(TreeNode node)
        {
            if (node == null)
                return 0;

            int leftDepth = GetMinDep(node.left);//左
            int rightDepth = GetMinDep(node.right);//右

            //中
            //当左子树为空，右子树不为空，这时并不是最低点
            if (node.left == null && node.right != null)
                return 1 + rightDepth;
            //当左子树不为空，右子树为空，这时也不是最低点
            if (node.left != null && node.right == null)
                return 1 + leftDepth;

            int result = 1 + Math.Min(leftDepth, rightDepth);
            return result;
        }


        //=============================力扣222 完全二叉树的节点个数
        //给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
        //完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
        //若最底层为第 h 层，则该层包含 1~ 2h 个节点。
        //思路：可以采用通用求二叉树节点个数的层序遍历和递归遍历的方法
        //      也可以采用完全二叉树单独的方法
        public int CountNodes(TreeNode root )
        {//思路：完全二叉树只有两种情况：1）满二叉树；2）最后一层叶子节点没有满
         //     对于情况1，可以直接用 2^树深度-1来计算，注意这里根节点深度为1
         //     对于情况2，分别递归左孩子和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后再按照情况1来计算

            if (root == null)
                return 0;
            TreeNode left = root.left;
            TreeNode right = root.right;

            int leftHeight = 0, rightHeight = 0;//初始为0，为下面求指数方便
            while(left != null)
            {
                left = left.left;
                leftHeight++;
            }
            while(right != null)
            {
                right = right.right;
                rightHeight++;
            }
            if (leftHeight == rightHeight)
                return (2 << leftHeight) - 1;//注意（2<<2)相当于 2^2，所以leftHeight初始为0
            return CountNodes(root.left) + CountNodes(root.right) + 1;
        }
        
        // ==============================力扣110 平衡二叉树
        //给定一个二叉树，判断它是否是高度平衡的二叉树
        //一颗高度平衡的二叉树定义为：一个二叉树的每个节点的左右两个子树的高度差的绝对值不超过1
        //递归
        //要比较高度，必然是后序遍历
        public bool IsBalanced(TreeNode root)
        {
            return GetDep(root) == -1 ? false : true;
        }
        //返回高度，如果当前节点不是平衡二叉树，则返回-1
        private int GetDep(TreeNode node)
        {
            if (node == null)
                return 0;

            int leftDepth = GetDep(node.left);//左
            if (leftDepth == -1)// 说明左子树已经不是二叉平衡树
                return -1;
            int rightDepth = GetDep(node.right);// 右
            if (rightDepth == -1)// 说明右子树已经不是二叉平衡树
                return -1;
            int result = 0;
            if (Math.Abs(leftDepth - rightDepth) > 1)// 中
                result = -1;
            else
                result = 1 + Math.Max(leftDepth, rightDepth);//以当前节点为根节点的最大高度

            return result;
        }

        //迭代法
        public bool IsBalanced_2(TreeNode root)
        {
            Stack<TreeNode> st = new Stack<TreeNode>();
            if (root == null)
                return true;
            st.Push(root);
            while(st.Count>0)
            {
                TreeNode node = st.Pop();//中
                if (Math.Abs(GetDep_2(node.left) - GetDep_2(node.right)) > 1)//判断左右孩子高度是否符合
                    return false;
                if (node.right != null)//右（空节点不入栈）
                    st.Push(node.right);
                if (node.left != null)//左（空节点不入栈）
                    st.Push(node.left);
            }
            return true;
        }
        //返回当前节点的最大深度，也就是当前节点的高度
        private int GetDep_2(TreeNode cur)
        {
            Stack<TreeNode> st = new Stack<TreeNode>();
            if (cur != null)
                st.Push(cur);
            int depth = 0;//记录深度
            int result = 0;
            while(st.Count > 0)
            {
                TreeNode node = st.Pop();
                if(node != null)
                {
                    st.Push(node);
                    st.Push(null);//中
                    depth++;
                    if (node.right != null)//右
                        st.Push(node.right);
                    if (node.left != null)//左
                        st.Push(node.left);
                }
                else
                {
                    node = st.Pop();
                    depth--;
                }
                result = result > depth ? result : depth;
            }
            return result;
        }


        //======================================力扣257 二叉树的所有路径
        //给定一个二叉树，返回所有从根节点到叶子节点的路径
        //思路：求从根节点到叶子节点，即需要前序遍历
        //递归法
        public IList<string> BinaryTreePaths(TreeNode root)
        {
            List<string> result = new List<string>();
            List<int> path = new List<int>();
            if (root == null)
                return result;
            Travesal(root, path, result);
            return result;
        }
        private void Travesal(TreeNode cur, List<int> path,List<string> result)
        {
            path.Add(cur.val);//中
            if (cur.left == null && cur.right == null)
            {//终止逻辑
                string sPath = "";
                for(int i = 0;i<path.Count - 1;i++)
                {//将paht记录的路径转为string格式
                    sPath += path[i];
                    sPath += "->";
                }
                sPath += path[path.Count - 1];//记录最后一个节点（叶子节点）
                result.Add(sPath);
                return;
            }

            
            if (cur.left != null)
            {
                Travesal(cur.left, path, result);
                path.RemoveAt(path.Count - 1);//回溯 移除最后一个
            }
                if (cur.right != null)
            {
                Travesal(cur.right, path, result);
                path.RemoveAt(path.Count - 1);//回溯 移除最后一个
            }
        }
        //迭代法
        public IList<string> BinaryTreePaths_2(TreeNode root)
        {
            Stack<TreeNode> treeSt = new Stack<TreeNode>();//保存树的遍历节点
            Stack<string> pathSt = new Stack<string>();//保存遍历路径的节点
            List<string> result = new List<string>();//保存最终路径集合
            if (root == null)
                return result;
            treeSt.Push(root);
            pathSt.Push(root.val.ToString());
            while(treeSt.Count > 0)
            {
                TreeNode node = treeSt.Pop();//取出节点 中
                string path = pathSt.Pop();//取出节点对应的路径
                if(node.left == null && node.right == null)
                {
                    result.Add(path);//遇到叶子节点
                }
                if(node.right != null)
                {
                    treeSt.Push(node.right);
                    pathSt.Push(path + "->" + node.right.val.ToString());
                }
                if(node.left != null)
                {
                    treeSt.Push(node.left);
                    pathSt.Push(path + "->" + node.left.val.ToString());
                }
            }
            return result;
        }



    }
}
